﻿#include "Rasterization.h"
#include "SoftRenderer.h"

/////////////////////////////////////////////////////
// FRasterizationCPU

void FRasterizationCPU::TrapezoidTriangle(TArray<FTrapezoid, TInlineAllocator<2>>& TrapezoidList,
	const FVertexToPixelInterpolants* V1, const FVertexToPixelInterpolants* V2, const FVertexToPixelInterpolants* V3)
{
	const FVertexToPixelInterpolants* TempV = V1;
	
	// 根据3个顶点的Y坐标进行排序, 排序后 V1.Y <= V2.Y <= V3.Y
	if (V1->ScreenPos.Y > V2->ScreenPos.Y) 
	{
		// 交换 V1, V2
		TempV = V1;
		V1 = V2;
		V2 = TempV;
	}

	if (V1->ScreenPos.Y > V3->ScreenPos.Y)
	{
		// 交换 V1, V3
		TempV = V1;
		V1 = V3;
		V3 = TempV;
	}

	if (V2->ScreenPos.Y > V3->ScreenPos.Y)
	{
		// 交换 V2, V3
		TempV = V2;
		V2 = V3;
		V3 = TempV;
	}

	// 如果3个顶点共线，不做光栅化
	if (V1->ScreenPos.Y == V2->ScreenPos.Y && V1->ScreenPos.Y == V3->ScreenPos.Y)
		return;
	
	if (V1->ScreenPos.X == V2->ScreenPos.X && V1->ScreenPos.X == V3->ScreenPos.X)
		return;

	// 如果是平顶三角形
	if (V1->ScreenPos.Y == V2->ScreenPos.Y)
	{
		if (V1->ScreenPos.X > V2->ScreenPos.X)
		{
			TempV = V1;
			V1 = V2;
			V2 = TempV;
		}

		FTrapezoid Trapezoid;
		Trapezoid.Top = V1->ScreenPos.Y;
		Trapezoid.Bottom = V3->ScreenPos.Y;
		Trapezoid.LeftEdge.Start = *V1;
		Trapezoid.LeftEdge.End = *V3;
		Trapezoid.RightEdge.Start = *V2;
		Trapezoid.RightEdge.End = *V3;
		TrapezoidList.Emplace(Trapezoid);
		return;
	}

	// 如果是平底三角形
	if (V2->ScreenPos.Y == V3->ScreenPos.Y)
	{
		if (V2->ScreenPos.X > V3->ScreenPos.X)
		{
			TempV = V2;
			V2 = V3;
			V3 = TempV;
		}

		FTrapezoid Trapezoid;
		Trapezoid.Top = V1->ScreenPos.Y;
		Trapezoid.Bottom = V3->ScreenPos.Y;
		Trapezoid.LeftEdge.Start = *V1;
		Trapezoid.LeftEdge.End = *V2;
		Trapezoid.RightEdge.Start = *V1;
		Trapezoid.RightEdge.End = *V3;
		TrapezoidList.Emplace(Trapezoid);
		return;
	}

	// 一般三角形的情况
	FTrapezoid Trapezoid0;
	Trapezoid0.Top = V1->ScreenPos.Y;
	Trapezoid0.Bottom = V2->ScreenPos.Y;

	FTrapezoid Trapezoid1;
	Trapezoid1.Top = V2->ScreenPos.Y;
	Trapezoid1.Bottom = V3->ScreenPos.Y;
	
	float K = (V3->ScreenPos.Y - V1->ScreenPos.Y) / (V2->ScreenPos.Y - V1->ScreenPos.Y);
	float X = V1->ScreenPos.X + (V2->ScreenPos.X - V1->ScreenPos.X) * K;
	
	if (X <= V3->ScreenPos.X)
	{
		// 左边为主
		Trapezoid0.LeftEdge.Start = *V1;
		Trapezoid0.LeftEdge.End = *V2;
		Trapezoid0.RightEdge.Start = *V1;
		Trapezoid0.RightEdge.End = *V3;
		
		Trapezoid1.LeftEdge.Start = *V2;
		Trapezoid1.LeftEdge.End = *V3;
		Trapezoid1.RightEdge.Start = *V1;
		Trapezoid1.RightEdge.End = *V3;
	}
	else
	{
		// 右边为主
		Trapezoid0.LeftEdge.Start = *V1;
		Trapezoid0.LeftEdge.End = *V3;
		Trapezoid0.RightEdge.Start = *V1;
		Trapezoid0.RightEdge.End = *V2;
		
		Trapezoid1.LeftEdge.Start = *V1;
		Trapezoid1.LeftEdge.End = *V3;
		Trapezoid1.RightEdge.Start = *V2;
		Trapezoid1.RightEdge.End = *V3;
	}

	TrapezoidList.Emplace(Trapezoid0);
	TrapezoidList.Emplace(Trapezoid1);
}

void FRasterizationCPU::ScanlineVertexInterp(FVertexToPixelInterpolants& LeftScanlineVertex,
	FVertexToPixelInterpolants& RightScanlineVertex, const FTrapezoid& Trapezoid, float Y)
{
	{
		const float LeftEdgeDeltaY = Trapezoid.LeftEdge.End.ScreenPos.Y - Trapezoid.LeftEdge.Start.ScreenPos.Y;

		// 左边顶点的插值比例
		const float LeftVertexWeight = (Y - Trapezoid.LeftEdge.Start.ScreenPos.Y) / LeftEdgeDeltaY;

		LeftScanlineVertex = FVertexToPixelInterpolants::LerpVertex(Trapezoid.LeftEdge.Start, Trapezoid.LeftEdge.End, LeftVertexWeight);
	}

	{
		const float RightEdgeDeltaY = Trapezoid.RightEdge.End.ScreenPos.Y - Trapezoid.RightEdge.Start.ScreenPos.Y;

		// 右边顶点的插值比例
		const float RightVertexWeight = (Y - Trapezoid.RightEdge.Start.ScreenPos.Y) / RightEdgeDeltaY;

		RightScanlineVertex = FVertexToPixelInterpolants::LerpVertex(Trapezoid.RightEdge.Start, Trapezoid.RightEdge.End, RightVertexWeight);
	}
}

FRasterizationCPU::FScanline FRasterizationCPU::InitScanline(const FVertexToPixelInterpolants& LeftScanlineVertex,
                                     const FVertexToPixelInterpolants& RightScanlineVertex, float Y)
{
	FScanline Scanline;

	const float Width = RightScanlineVertex.ScreenPos.X - LeftScanlineVertex.ScreenPos.X;
	Scanline.X = static_cast<int32>(LeftScanlineVertex.ScreenPos.X + 0.5f);
	Scanline.W = static_cast<int32>(RightScanlineVertex.ScreenPos.X + 0.5f) - Scanline.X;
	Scanline.Y = Y;
	
	Scanline.Vertex = LeftScanlineVertex;
	
	if (LeftScanlineVertex.ScreenPos.X >= RightScanlineVertex.ScreenPos.X)
	{
		Scanline.W = 0;
	}
	
	Scanline.Step = FVertexToPixelInterpolants::GetStepVertex(LeftScanlineVertex, RightScanlineVertex, Width);

	return Scanline;
}

void FRasterizationCPU::FillScanline(FScanline& Scanline, UFrameBuffer* FrameBuffer)
{
	for (int32 X = Scanline.X, Width = Scanline.W;  Width > 0; ++X, --Width)
	{
		if (X >= 0 && X < FrameBuffer->Width)
		{
			const float RHW = Scanline.Vertex.RHW;
			const float W = 1.0f / RHW;
			FrameBuffer->Point(X, Scanline.Y, Scanline.Vertex.Color * W);
		}

		FVertexToPixelInterpolants::StepVertex(Scanline.Vertex, Scanline.Step);
		
		if (X >= FrameBuffer->Width)
			break;
	}
}

void FRasterizationCPU::FillTrapezoid(const FTrapezoid& Trapezoid, UFrameBuffer* FrameBuffer)
{
	// 获取梯形顶部的像素坐标，四舍五入
	const int32 Top = static_cast<int32>(Trapezoid.Top + 0.5f);

	// 获取梯形底部的像素坐标，四舍五入
	const int32 Bottom = static_cast<int32>(Trapezoid.Bottom + 0.5f);

	// 逐扫描线填充梯形
	for (int32 Index = Top; Index < Bottom; ++Index)
	{
		if (Index >= 0 && Index < FrameBuffer->Height)
		{
			// 1 获取当前扫描线和梯形左右两条边相交的两个顶点数据

			// 扫描线和梯形左边相交的插值顶点信息
			FVertexToPixelInterpolants LeftScanlineVertex;
			
			// 扫描线和梯形右边相交的插值顶点信息
			FVertexToPixelInterpolants RightScanlineVertex;

			// 这里的Index需要加0.5是因为要对其像素的中心点，Index是当前扫描线的整数像素高度坐标
			// 转化为浮点数需要对其像素的中心，需要加上0.5
			ScanlineVertexInterp(LeftScanlineVertex, RightScanlineVertex, Trapezoid,  Index + 0.5f);

			// 2 初始化当前扫描线
			FScanline Scanline = InitScanline(LeftScanlineVertex, RightScanlineVertex, Index);
			
			// 3 填充扫描线像素
			FillScanline(Scanline, FrameBuffer);
		}

		// 扫描线高度超出FrameBuffer的高度就停止光栅化
		if (Index >= FrameBuffer->Height)
		{
			break;
		}
	}
}

void FRasterizationCPU::RasterizeTriangle(USoftRenderer* SoftRenderer, const FVertexToPixelInterpolants& V1, const FVertexToPixelInterpolants& V2, const FVertexToPixelInterpolants& V3)
{
	TArray<FTrapezoid, TInlineAllocator<2>> TrapezoidList;
	TrapezoidTriangle(TrapezoidList, &V1, &V2, &V3);

	for (int32 Index = 0, Count = TrapezoidList.Num(); Index < Count; ++Index)
	{
		FillTrapezoid(TrapezoidList[Index], SoftRenderer->FrameBuffer);
	}
}

/////////////////////////////////////////////////////
// FRasterizationGPU

FFix32 FRasterizationGPU::EdgeFunction(const FVector2Fix32& Edge0, const FVector2Fix32& Edge1)
{
	return FVector2Fix32::CrossProduct(Edge0, Edge1);
}

float FRasterizationGPU::EdgeFunction(const FVector2D& Edge0, const FVector2D& Edge1)
{
	return FVector2D::CrossProduct(Edge0, Edge1);
}

void FRasterizationGPU::RasterizeTriangle(USoftRenderer* SoftRenderer, const FVertexToPixelInterpolants* V1,
	const FVertexToPixelInterpolants* V2, const FVertexToPixelInterpolants* V3, USoftRendererShader* PixelShader, const FRenderObjectMaterial& Material)
{
	// 判断三角形朝向
	const FVector4 Dir12 = V2->Position - V1->Position;
	const FVector4 Dir13 = V3->Position - V1->Position;
	const FVector4 Normal = Dir12 ^ Dir13;  // 计算 Dir12 和 Dir13 的叉积

	// 默认采用的顺序是顺时针顶点顺序
	// DirectX的屏幕坐标系采用的右手坐标系， X 向右  Y 向下  Z 屏幕向里
	// 如果背向视点，则交换顶点，保证 edge equation 判断的符号为正
	if (Normal.Z > 0.0f)
	{
		const FVertexToPixelInterpolants* TempV = V2;
		V2 = V3;
		V3 = TempV;
	}
	else if (Normal.Z == 0.0f)
	{
		return;
	}
	
	// 计算每一个顶点的整数屏幕坐标：加 0.5 的偏移取屏幕像素方格中心对齐，其实就是四舍五入
	const FIntPoint ScreenPosInPixels1 = FIntPoint( static_cast<int32>(V1->ScreenPos.X + 0.5f), static_cast<int32>(V1->ScreenPos.Y + 0.5f));
	const FIntPoint ScreenPosInPixels2 = FIntPoint( static_cast<int32>(V2->ScreenPos.X + 0.5f), static_cast<int32>(V2->ScreenPos.Y + 0.5f));
	const FIntPoint ScreenPosInPixels3 = FIntPoint( static_cast<int32>(V3->ScreenPos.X + 0.5f), static_cast<int32>(V3->ScreenPos.Y + 0.5f));
	
	// 计算三角形面积，为零就退出
	if (FMath::Abs(FVector2D::CrossProduct(ScreenPosInPixels2 - ScreenPosInPixels1, ScreenPosInPixels3 - ScreenPosInPixels2)) <= 0)
		return;

	// 计算三角形的外接像素矩形
	auto FrameBuffer = SoftRenderer->FrameBuffer;
	FIntPoint Min = FIntPoint(INT_MAX, INT_MAX);   // 矩形的左上角像素坐标 
	FIntPoint Max = FIntPoint(INT_MIN, INT_MIN);   // 矩形的右下角像素坐标
	{
		Min.X = FMath::Min(FrameBuffer->Width - 1, FMath::Min(Min.X, ScreenPosInPixels1.X));
		Min.Y = FMath::Min(FrameBuffer->Height - 1, FMath::Min(Min.Y, ScreenPosInPixels1.Y));
		Max.X = FMath::Max(FrameBuffer->Width - 1, FMath::Max(Max.X, ScreenPosInPixels1.X));
		Max.Y = FMath::Max(FrameBuffer->Height - 1, FMath::Max(Max.Y, ScreenPosInPixels1.Y));

		Min.X = FMath::Min(FrameBuffer->Width - 1, FMath::Min(Min.X, ScreenPosInPixels2.X));
		Min.Y = FMath::Min(FrameBuffer->Height - 1, FMath::Min(Min.Y, ScreenPosInPixels2.Y));
		Max.X = FMath::Max(FrameBuffer->Width - 1, FMath::Max(Max.X, ScreenPosInPixels2.X));
		Max.Y = FMath::Max(FrameBuffer->Height - 1, FMath::Max(Max.Y, ScreenPosInPixels2.Y));

		Min.X = FMath::Min(FrameBuffer->Width - 1, FMath::Min(Min.X, ScreenPosInPixels3.X));
		Min.Y = FMath::Min(FrameBuffer->Height - 1, FMath::Min(Min.Y, ScreenPosInPixels3.Y));
		Max.X = FMath::Max(FrameBuffer->Width - 1, FMath::Max(Max.X, ScreenPosInPixels3.X));
		Max.Y = FMath::Max(FrameBuffer->Height - 1, FMath::Max(Max.Y, ScreenPosInPixels3.Y));
	}

	const FVector2Fix32 Fix32ScreenPos1 = FVector2Fix32(V1->ScreenPos);
	const FVector2Fix32 Fix32ScreenPos2 = FVector2Fix32(V2->ScreenPos);
	const FVector2Fix32 Fix32ScreenPos3 = FVector2Fix32(V3->ScreenPos);
	
	const FVector2Fix32 E12 = FVector2Fix32(Fix32ScreenPos2 - Fix32ScreenPos1);
	const FVector2Fix32 E23 = FVector2Fix32(Fix32ScreenPos3 - Fix32ScreenPos2);
	const FVector2Fix32 E31 = FVector2Fix32(Fix32ScreenPos1 - Fix32ScreenPos3);
	
	const FVector2Fix32 TopLeftPoint = FVector2Fix32(Min) + FVector2Fix32(FFix32::Fix32_HalfOne, FFix32::Fix32_HalfOne);
	FFix32 F12 = EdgeFunction(E12, TopLeftPoint - Fix32ScreenPos1);
	FFix32 F23 = EdgeFunction(E23, TopLeftPoint - Fix32ScreenPos2);
	FFix32 F31 = EdgeFunction(E31, TopLeftPoint - Fix32ScreenPos3);
	
	FFix32 DeltaX12 = Fix32ScreenPos1.Y - Fix32ScreenPos2.Y;
	FFix32 DeltaY12 = Fix32ScreenPos2.X - Fix32ScreenPos1.X;
	FFix32 DeltaX23 = Fix32ScreenPos2.Y - Fix32ScreenPos3.Y;
	FFix32 DeltaY23 = Fix32ScreenPos3.X - Fix32ScreenPos2.X;
	FFix32 DeltaX31 = Fix32ScreenPos3.Y - Fix32ScreenPos1.Y;
	FFix32 DeltaY31 = Fix32ScreenPos1.X - Fix32ScreenPos3.X;

	auto DepthStencilBuffer = SoftRenderer->DepthStencilBuffer;
	
	// 1
	// 不能单纯的采用浮点数计算边界函数，由于浮点数精度误差问题
	// f >= 0 的判断不稳定，导致可能有些不该点亮的像素被点亮，该被点亮的像素没被点亮
	
	// 2
	// 这里不能用整数坐标来计算，网上有很多教程用整数坐标计算的，实际有问题，导致像素计算不精准了
	// 我提了一个issue给他们 https://github.com/skywind3000/RenderHelp/issues/10
	
	// 迭代三角形外接矩形的所有点
	for (int32 Y = Min.Y; Y <= Max.Y; ++Y)
	{
		FFix32 EX1 = F12;
		FFix32 EX2 = F23;
		FFix32 EX3 = F31;

		for (int32 X = Min.X; X <= Max.X; ++X)
		{
			// 比如一个像素(0, 0)坐标处，转换为浮点数需要转换像素中心的浮点数坐标(0.5, 0.5)
			FVector2D Pixel = FVector2D(X + 0.5f, Y + 0.5f);
			
			if (EX1 >= 0 && EX2 >= 0 && EX3 >= 0)
			{
				// 三个顶点到当前点的矢量
				FVector2D S0 = V1->ScreenPos - Pixel;
				FVector2D S1 = V2->ScreenPos - Pixel;
				FVector2D S2 = V3->ScreenPos - Pixel;

				// 重心坐标系：计算内部子三角形面积 A / B / C
				float A = FMath::Abs(FVector2D::CrossProduct(S1, S2));    // 子三角形 Px-P1-P2 面积
				float B = FMath::Abs(FVector2D::CrossProduct(S2, S0));    // 子三角形 Px-P2-P0 面积
				float C = FMath::Abs(FVector2D::CrossProduct(S0, S1));    // 子三角形 Px-P0-P1 面积
				float S = A + B + C;                    // 大三角形 P0-P1-P2 面积

				if (S > 0.0f)
				{
					// 除以总面积，以保证：a + b + c = 1，方便用作插值系数
					A = A * (1.0f / S);
					B = B * (1.0f / S);
					C = C * (1.0f / S);

					// 计算当前点的 1/w，因 1/w 和屏幕空间呈线性关系，故直接重心插值
					float RHW = V1->RHW * A + V2->RHW * B + V3->RHW * C;
					
					// 还原当前像素的 w
					float W = 1.0f / ((RHW != 0.0f) ? RHW : 1.0f);

					// 计算三个顶点插值 varying 的系数
					// 先除以各自顶点的 w 然后进行屏幕空间插值然后再乘以当前 w
					float C0 = V1->RHW * A * W;
					float C1 = V2->RHW * B * W;
					float C2 = V3->RHW * C * W;

					// 插值出新的顶点
					auto NewVertex = FVertexToPixelInterpolants::InterpVertex(*V1, *V2, *V3, C0, C1, C2, RHW);

					float ZDepth = 0;
					bool bEnableEarlyZ = false;
					
					// 早期深度测试
					{
						// 检查是否开启早期深度测试功能
						bEnableEarlyZ = SoftRenderer->bEnableDepthTest && SoftRenderer->bEnableEarlyZ;
						if (bEnableEarlyZ)
						{
							// 开启AlphaTest的时候, 不能以用EarlyZ
							bEnableEarlyZ = !PixelShader->bDiscardPixel;
						}

						// 执行早期深度测试
						if (bEnableEarlyZ && !DepthTest(SoftRenderer->DepthBufferType, NewVertex, X, Y, DepthStencilBuffer, Material, ZDepth))
						{
							EX1 += DeltaX12;
							EX2 += DeltaX23;
							EX3 += DeltaX31;
							continue;
						}
					}
					
					// 对每一个像素执行像素着色器
					bool bDiscardCurPixel = false;
					FLinearColor TargetColor = PixelShader->RunPixelShader(NewVertex, bDiscardCurPixel);

					// Alpha Test 操作
					{
						if (bDiscardCurPixel)
						{
							EX1 += DeltaX12;
							EX2 += DeltaX23;
							EX3 += DeltaX31;
							continue;
						}
					}
					
					// 深度操作
					{
						// 如果早期深度测试没有执行并且需要开启深度测试, 在标准流程这里执行一个深度测试
						const bool bEnableLateZ = SoftRenderer->bEnableDepthTest && !bEnableEarlyZ;
						if (bEnableLateZ && !DepthTest(SoftRenderer->DepthBufferType, NewVertex, X, Y, DepthStencilBuffer, Material, ZDepth))
						{
							EX1 += DeltaX12;
							EX2 += DeltaX23;
							EX3 += DeltaX31;
							continue;
						}

						// 写入深度缓存
						if (Material.bDepthWrite)
						{
							DepthStencilBuffer->SetDepthValue(X, Y, ZDepth);
						}
					}
					
					FrameBuffer->Point(X, Y, TargetColor);
				}
			}

			EX1 += DeltaX12;
			EX2 += DeltaX23;
			EX3 += DeltaX31;
		}

		F12 += DeltaY12;
		F23 += DeltaY23;
		F31 += DeltaY31;
	}
}

bool FRasterizationGPU::DepthTest(ESoftRendererDepthBufferType DepthBufferType, const FVertexToPixelInterpolants& Vertex, const int32 X, const int32 Y,
	const UDepthStencilBuffer* DepthStencilBuffer, const FRenderObjectMaterial& Material, float& ZDepth)
{
	if (DepthBufferType == ESoftRendererDepthBufferType::WBuffer)
	{
		// W-Buffer目前不适合正交投影, 正交投影所有RHW都是1
		// 导致正交投影下有严重的z-fighting现象,也可以判断正交投影矩阵后在用Vertex.Position.Z来兼容处理,由于实际多用z-buffer,这里不考虑兼容正交投影的w-buffer
		// 实际主流游戏引擎基本都是用ReversedZ, 包括Unity引擎和UE引擎
		// https://www.mvps.org/directx/articles/using_w-buffers.htm
		// https://learn.microsoft.com/en-us/windows-hardware/drivers/display/w-buffering
		// TODO 填充代码
	}
	else
	{
		// TODO 填充代码
	}

	bool bDepthTestPass = false;

	// TODO 填充代码
	
	return bDepthTestPass;
}

/////////////////////////////////////////////////////
